package 每日一题;

import 链表.ListNode;

public class No148排序链表 {

    /**
     * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
     * 进阶：
     * 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
     *
     * 示例 1：
     * 输入：head = [4,2,1,3]
     * 输出：[1,2,3,4]
     * 示例 2：
     * 输入：head = [-1,5,3,4,0]
     * 输出：[-1,0,3,4,5]
     * 示例 3：
     * 输入：head = []
     * 输出：[]
     *  
     * 提示：
     * 链表中节点的数目在范围 [0, 5 * 104] 内
     * -105 <= Node.val <= 105
     */

    public ListNode sortList(ListNode head) {
        /**
         * 思路:
         * 中间切割,递归切割到底;
         * 然后开始合并两个有序链表;
         * 然后返回合并后的链表,继续递归。
         */
        return splitListNode(head);
    }

    private ListNode splitListNode(ListNode node) {
        if(node==null||node.next==null){
            return node;
        }

        //寻找中间节点,分割
        ListNode minNode=findMidNode(node);
        ListNode rightNode=minNode.next;
        minNode.next=null;
        ListNode leftNode = splitListNode(node);
        rightNode=splitListNode(rightNode);

        //合并
        return mergeListNode(leftNode,rightNode);
    }

    private ListNode findMidNode(ListNode node) {
        ListNode last=node;
        ListNode slow=node;
        ListNode fast=node;

        while (fast!=null&&fast.next!=null){
            last=slow;
            slow=slow.next;
            fast=fast.next.next;
        }

        return last;
    }

    private ListNode mergeListNode(ListNode leftNode,ListNode rightNode) {

        ListNode cur1=leftNode;
        ListNode cur2=rightNode;
        ListNode dump=new ListNode(-1);
        ListNode lastNode=dump;
        ListNode cur;

        while (cur1!=null&&cur2!=null){

            if(cur1.val<cur2.val){
                cur=cur1;
                cur1=cur1.next;
            }else{
                cur=cur2;
                cur2=cur2.next;
            }

            lastNode.next=cur;
            lastNode=cur;

        }

        if(cur1!=null){
            lastNode.next=cur1;
        }else{
            lastNode.next=cur2;
        }

        return dump.next;
    }

    public static void main(String[] args) {
        No148排序链表 n=new No148排序链表();
        ListNode listNode = ListNode.createListNode(new int[]{4, 2, 1, 3});
        ListNode result = n.sortList(listNode);
        ListNode.printListNode(result);
    }

}
